
/*
Date:20220221 19:02PM
key；1.每碰到一个char是三个当中的哪一个分类讨论怎么操作
     2.所有的栈问题都是最终遍历结束栈内仍可能有剩余，最后这部分记得处理
     3.原计划用string存最终结果，然而过程要频繁地扩容s=s+c。既然最开始的字符串与最终字符串大小相同。
     直接开一个固定大小的空间存即可。
     4.时空复杂度都是O(N)
*/
class Solution {
public:
    void StackClear(stack<char>&s)
    {
        while(!s.empty()){s.pop();}
    }
    string pushDominoes(string dominoes) {
        //唯一用到的栈
        stack<char>S;
        //存出栈结果的vector
        vector<char>V;
        V.resize(dominoes.size());
        //全局vector的指针
        int I=0;
        //用以标识栈内是否有R
        bool R_status=false;
        for(char c:dominoes)
        {
            if(c=='L')
            {
                if(S.empty())
                {
                    V[I++]=c;
                    //final=final+c;
                }
                else{
                    if(R_status)
                    {
                        int total=S.size();
                        if(total%2==0)
                        {
                            for(int i=0;i<(total)/2;i++)
                            {
                                V[I++]='R';
                                //final=final+'R';
                            }
                            V[I++]='.';
                            //final=final+'.';
                            for(int i=0;i<(total)/2;i++)
                            {
                                V[I++]=c;
                                //final=final+c;
                            }
                        }
                        else{
                            for(int i=0;i<(total+1)/2;i++)
                            {
                                V[I++]='R';
                                //final=final+'R';
                            }
                            for(int i=0;i<(total+1)/2;i++)
                            {
                                V[I++]=c;
                                //final=final+c;
                            }
                        }
                        R_status=false;
                    }
                    else
                    {
                        for(int i=0;i<S.size()+1;i++)
                        {
                            V[I++]=c;
                                //final=final+c;
                        }
                        
                    }
                    StackClear(S);
                }
                continue;
            }
            if(c=='R')
            {
                if(S.empty())
                {
                    
                }
                else
                {
                    char tmp_c;
                    if(R_status)
                    {
                        tmp_c='R';
                        
                    }
                    else
                    {
                        tmp_c='.';
                    }
                    for(int i=0;i<S.size();i++)
                    {
                        V[I++]=tmp_c;
                                
                    }
                    StackClear(S);
                }
                S.push(c);
                R_status=true;
            }
            else
            {
                S.push(c);
            }

        }
        
        if(!S.empty())
        {
            char tmp_c;
            if(R_status)
            {
                tmp_c='R';
            }
            else
            {
                tmp_c='.';
            }
            for(int i=0;i<S.size();i++)
            {
                V[I++]=tmp_c;
            }
        }
        for(int i=0;i<dominoes.size();i++)
        {
            dominoes[i]=V[i];
        }
        return dominoes;
    }
};
